package com.cloud.code.算法.排序.归并排序;

import java.util.Arrays;

//归并排序：  思想就是大的问题，分成小的问题 ，逐个解决
public class mergeSort {

    public static void main(String[] args) {

        int[] arr = {2, 1, 4, 2, 5, 7, 3};

        sort(arr, 0, arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int start, int end) {

        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        sort(arr, start, mid);
        sort(arr, mid + 1, end);

        merge(arr, start, mid, end);

    }

    private static void merge(int[] arr, int l, int mid, int r) {

        int[] temps = Arrays.copyOfRange(arr, l, r + 1);

        int i = l;
        int j = mid + 1;

        for (int k = l; k <= r; k++) {

            if (i > mid) {
                arr[k] = temps[j-l];
                j++;
            } else if (j > r) {
                arr[k] = temps[i-l];
                i++;
            } else if (temps[i-l] < temps[j-l]) {
                arr[k] = temps[i-l];
                i++;
            } else {
                arr[k] = temps[j-l];
                j++;
            }
        }

    }

}
